README.md

767. Reorganize String

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement ofsor return""if not possible.

Example 1:

Input: s = "aab" Output: "aba" 

Example 2:

Input: s = "aaab" Output: "" 

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters.

Solutions (Rust)

1. Solution

use std::collections::BinaryHeap;implSolution{pubfnreorganize_string(s:String) -> String{letmut count = [0;26];letmut heap = BinaryHeap::new();letmut ret = vec![];for ch in s.bytes(){ count[(ch - b'a')asusize] += 1;}for ch inb'a'..=b'z'{ heap.push((count[(ch - b'a')asusize], ch));}for _ in0..s.len(){let(count0, ch0) = heap.pop().unwrap();if*ret.last().unwrap_or(&0) != ch0 { ret.push(ch0); heap.push((count0 - 1, ch0));}elseif heap.peek().unwrap().0 == 0{returnString::new();}else{let(count1, ch1) = heap.pop().unwrap(); ret.push(ch1); heap.push((count1 - 1, ch1)); heap.push((count0, ch0));}}String::from_utf8(ret).unwrap()}}